#pragma once
#include <iostream>
using namespace std;

namespace xzq
{
    template <class K>
    struct BSTreeNode
    {
        BSTreeNode<K> *_left;
        BSTreeNode<K> *_right;
        K _key;
        BSTreeNode(const K &key)
            : _left(nullptr), _right(nullptr), _key(key)
        {
        }
    };

    template <class K>
    class BSTree
    {
        typedef BSTreeNode<K> Node;

    public:
        bool Insert(const K &key)
        {
            if (_root == nullptr)
            {
                _root = new Node(key);
                return true;
            }
            Node *parent = nullptr;
            Node *cur = _root;
            while (cur)
            {
                if (cur->_key < key)
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else if (cur->_key > key)
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else
                {
                    return false;
                }
            }
            cur = new Node(key);
            if (parent->_key < key)
                parent->_right = cur;
            else
                parent->_left = cur;
            return true;
        }
        bool Find(const K &key)
        {
            Node *cur = _root;
            while (cur)
            {
                if (cur->_key < key)
                {
                    cur = cur->_right;
                }
                else if (cur->_key > key)
                {
                    cur = cur->_left;
                }
                else
                {
                    return true;
                }
            }
            return false;
        }
        bool Erase(const K &key)
        {
            Node *parent = nullptr;
            Node *cur = _root;
            while (cur)
            {
                if (cur->_key < key)
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else if (cur->_key > key)
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else
                {
                    if (cur->_left == nullptr)
                    {
                        if (cur == _root)
                        {
                            _root = cur->_right;
                        }
                        else
                        {
                            if (parent->_right == cur)
                                parent->_right = cur->_right;
                            else
                                parent->_left = cur->_right;
                        }
                        delete cur;
                    }
                    else if (cur->_right == nullptr)
                    {
                        if (cur == _root)
                        {
                            _root = _root->_left;
                        }
                        else
                        {
                            if (parent->_right == cur)
                                parent->_right = cur->_left;
                            else
                                parent->_left = cur->_left;
                        }
                        delete cur;
                    }
                    else
                    {
                        Node *rightMinparent = cur;
                        Node *rightMin = cur->_right;
                        while (rightMin->_left)
                        {
                            rightMinparent = rightMin;
                            rightMin = rightMin->_left;
                        }
                        cur->_key = rightMin->_key;
                        if (rightMinparent->_left == rightMin)
                            rightMinparent->_left = rightMin->_right;
                        else
                            rightMinparent->_right = rightMin->_right;
                        delete rightMin;
                    }
                    return true;
                }
            }
            return false;
        }
        void _Inorder(Node *root)
        {
            if (root == nullptr)
                return;
            _Inorder(root->_left);
            cout << root->_key << " ";
            _Inorder(root->_right);
        }
        void Inorder()
        {
            _Inorder(_root);
            cout << endl;
        }

    private:
        Node *_root = nullptr;
    };
void test()
{
    BSTree<int> t;
    int a[] = {5,3,4,1,7,8,2,6,0,9};
    for(auto e : a)
    {
        t.Insert(e);
    }
    t.Inorder();
    t.Erase(2);
    t.Inorder();
    t.Erase(8);
    t.Inorder();
    t.Erase(1);
    t.Inorder();
    t.Erase(5);
    t.Inorder();
    t.Erase(7);
    t.Inorder();
    if(t.Find(9))
    {
        cout<<"找到了"<<endl;
    }
    if(!t.Find(100))
    {
        cout<<"没找到"<<endl;
    }
}
}